#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <cstring>
#include <vector>
#include<queue>
using namespace std;
#define MAXL 100005
int n, m, s, u, v, w;
int dis[MAXL], vis[MAXL];
struct node
{
	int v, w;
};
struct eode {
	int dis, u;
	bool operator>(const eode& e) const 
	{
		return dis > e.dis;
	}
};
vector<node>a[MAXL];
priority_queue<eode, vector<eode>, greater<eode> > q;
void dijkstra()
{
	memset(dis, 63, sizeof(dis));
	dis[s] = 0;
	q.push({ 0,s });
	while (!q.empty())
	{
		int u = q.top().u;//!!!!!!!!!!!!!
		q.pop();
		if (vis[u])
			continue;
		vis[u] = 1;
		for (auto ed : a[u])//!!!!!!!!!!!!!!!
		{
			int v = ed.v;
			int w = ed.w;
			if (dis[v] > dis[u] + w)
			{
				dis[v] = dis[u] + w;
			}
			if (!vis[v])
			{
				q.push({ dis[v], v });
			}
		}
	}
}
int main()
{
	cin >> n >> m >> s;
	for (int i = 0; i < m; i++)
	{
		cin >> u >> v >> w;
		a[u].push_back({ v,w });
	}
	dijkstra();
	for (int i = 1; i <= n; i++)
	{
		cout << dis[i] << " ";
	}
	return 0;
}